package leetCode.firstWeek;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Code_39 {
  List<List<Integer>> res = new LinkedList<>();
  List<Integer> ini = new ArrayList<>();

  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    findArr(candidates, target, 0);
    return res;
  }

  public void findArr(int[] candidates, int target, int start) {
    if (target < 0) {
      return;
    }
    if (target == 0) {
      res.add(new ArrayList<>(ini));
      return;
    }
    if (target > 0) {
      for (int i = start; i < candidates.length; i++) {
        ini.add(candidates[i]);
        findArr(candidates, target - candidates[i], i);
        ini.remove(ini.size() - 1);
      }
    }
    return;
  }
}
